#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

typedef struct Node
{
    int tag; //标志域
    union
    {
        char atom; //原子结点的值域
        struct
        {
            struct Node *hp, *tp;
        } ptr; //子表结点的指针域，hp指向表头；tp指向表尾
    } un;
} GList;

GList *create_Atom(GList *L, char str)
{
    // 设置本节点的标识域
    L->tag = 1;

    // 开辟原子域空间
    L->un.ptr.hp = (GList *)malloc(sizeof(GList));

    // 设置原子域的标志域
    L->un.ptr.hp->tag = 0;

    // 设置原子域的原子值
    L->un.ptr.hp->un.atom = str;

    // 为本节点尾指针开辟空间
    L->un.ptr.tp = (GList *)malloc(sizeof(GList));
    // 返回本节点的尾指针
    return L->un.ptr.tp;
}

GList *create_List(GList *L)
{
    // 设置本节点的标识域
    L->tag = 1;
    // 设置本节点的尾指针
    L->un.ptr.tp = NULL;
    // 创建子节点并开辟空间
    L->un.ptr.hp = (GList *)malloc(sizeof(GList));
    // 返回子节点的头指针
    return L->un.ptr.hp;
}

GList *create_GList_Example()
{

    // 创建广义表(a,(b,c,d))
    GList *c = (GList *)malloc(sizeof(GList));
    GList *c_bcd_tail = create_Atom(c, 'a');
    GList *bNodef = create_List(c_bcd_tail);
    GList *bNode = create_Atom(bNodef, 'b');
    GList *cNode = create_Atom(bNode, 'c');
    GList *dNode = create_Atom(cNode, 'd');

    return c;
}

GList *Get_Head(GList *L)
{
    GList *head = L->un.ptr.hp;

    return head;
}

GList *Get_Tail(GList *L)
{
    GList *tail = L->un.ptr.tp;
    return tail;
}

int GListTraverse(GList *L)
{

    if (L == NULL)
    {
        return 0;
    }
    // 如果该节点为原子节点，打印
    if (L->tag == 0)
    {
        printf("%c", L->un.atom);
    }
    // 如果该节点为表节点，递归函数
    else if (L->tag == 1)
    {
        GListTraverse(L->un.ptr.hp);
        GListTraverse(L->un.ptr.tp);
    }
}

int GList_Depth(GList *L)
{
    int depth = 1;

    if (L == NULL)
    {
        return depth;
    }

    // 如果该节点为表节点，递归函数
    if (L->tag == 1)
    {
        depth++;
        GList_Depth(L->un.ptr.tp);
    }

    return depth;
}

int main()
{
    GList *c = create_GList_Example();

    // 手动打印
    printf("%c", c->un.ptr.hp->un.atom);
    printf("%c", c->un.ptr.tp->un.ptr.hp->un.ptr.hp->un.atom);
    printf("%c", c->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp->un.atom);
    printf("%c\n", c->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp->un.atom);

    // 测试取头操作
    GList *head = Get_Head(c);
    GListTraverse(head);

    putchar('\n');

    // 测试取尾操作
    GList *tail = Get_Tail(c);
    GListTraverse(tail);

    putchar('\n');

    // 测试取深度
    int depth;
    depth = GList_Depth(c);
    printf("%d\n", depth);
    return 0;
}